Semi-labeled trees are phylogenies whose internal nodes may be labeled byhigher-order taxa. Thus, a leaf labeled Mus musculus could nest within asubtree whose root node is labeled Rodentia, which itself could nest within asubtree whose root is labeled Mammalia. Suppose we are given collection$\mathcal P$ of semi-labeled trees over various subsets of a set of taxa. Theancestral compatibility problem asks whether there is a semi-labeled tree$\mathcal T$ that respects the clusterings and the ancestor/descendantrelationships implied by the trees in $\mathcal P$. We give a$\tilde{O}(M_{\mathcal{P}})$ algorithm for the ancestral compatibility problem,where $M_{\mathcal{P}}$ is the total number of nodes and edges in the trees in$\mathcal P$. Unlike the best previous algorithm, the running time of ourmethod does not depend on the degrees of the nodes in the input trees.
展开▼
机译：半标记树是系统树，其内部节点可能被高阶分类单元标记。因此，标记为小家鼠的叶子可以嵌套在其根节点被标记为Rodentia的子树中，而其本身可以嵌套在其根被标记为Mammalia的子树中。假设我们得到了一组分类单元的各个子集上的半标签树的集合\\数学P $。祖先兼容性问题询问是否有一个半标记的tree $ \ mathcal T $尊重$ \ mathcal P $中树所隐含的聚类和祖先/去世关系。对于祖先兼容性问题，我们给出了$ \ tilde {O}（M _ {\ mathcal {P}}）$算法，其中$ M _ {\ mathcal {P}} $是树中节点和边的总数$ \数学P $。与以前的最佳算法不同，我们的方法的运行时间不取决于输入树中节点的程度。
展开▼
